package geometry;

import java.util.Random;

public class Convex {

	static final double eps = 1e-9;

	static Random ran = new Random();

	int scan(int a[][], int n) {
		assert (n == a.length);
		sort(a, 0, n - 1);
		int stack[] = new int[n + 1];
		int top = 0;
		stack[top++] = 0;
		stack[top++] = 1;
		int p, q;
		int i = 2;
		double cross;
		while (i < n) {
			while (top > 1) {
				p = stack[top - 1];
				q = stack[top - 2];
				cross = cross_product(a[p][0] - a[q][0], a[p][1] - a[q][1],
						a[i][0] - a[q][0], a[i][1] - a[q][1]);
				if (cross + eps < 0)
					break;
				top--;
			}
			stack[top++] = i++;
		}
		stack[top++] = n - 2;
		i = n - 3;
		while (i >= 0) {
			while (top > 1) {
				p = stack[top - 1];
				q = stack[top - 2];
				cross = cross_product(a[p][0] - a[q][0], a[p][1] - a[q][1],
						a[i][0] - a[q][0], a[i][1] - a[q][1]);
				if (cross + eps < 0)
					break;
				top--;
			}
			stack[top++] = i--;
		}
		if (top < 3)
			return -1;
		return top - 1;
	}

	static void sort(int a[][], int q, int r) {
		if (q >= r)
			return;
		int p = partition(a, q, r);
		sort(a, q, p - 1);
		sort(a, p + 1, r);
	}

	static int partition(int a[][], int q, int r) {
		int p = ran.nextInt(r - q + 1) + q;
		int i = q, j = q;
		swap(a, p, r);
		while (i < r) {
			if (a[i][0] < a[r][0] || a[i][0] == a[r][0] && a[i][1] < a[r][1]) {
				swap(a, i, j);
				j++;
			}
			i++;
		}
		swap(a, j, r);
		return j;
	}

	static void swap(int a[][], int i, int j) {
		int tmp[] = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	double cross_product(double x1, double y1, double x2, double y2) {
		return x1 * y2 - y1 * x2;
	}

	boolean equal(double a, double b) {
		return Math.abs(a - b) < eps;
	}

}
